1. Field of the Invention
The invention relates to image generation methods and related image processing systems, and more particularly, to a halftone image generation method and a related image processing system for converting a grayscale image into a halftone image.
2. Description of the Related Art
Digital halftoning is a technique employing digital image processing to produce a halftoned input digital image from an input digital image. An input digital image normally consists of pixels of discrete values typically ranging from 0 to 255. To reproduce this image on an output device capable of printing dots of one gray level (e.g. black), it is necessary to convert the input digital image to a halftoned digital image using some form of halftoning techniques. Halftoning methods rely on the fact that for sight of an observer, vision will be spatially averaged over some local area of the halftoned digital image so that intermediate gray levels can be created by turning some of the pixels “on” and some of the pixels “off” in some small region of the halftoned digital image. The fraction of the pixels that are turned on will determine the apparent gray level.
Existing digital halftoning techniques can be classified into three main categories: (1) dithering, (2) error diffusion, and (3) iterative optimization. Each of these techniques, as well as combinations of the techniques, has its own advantages and shortcomings. Generally speaking, since the iterative optimization technique demands a much higher computational procedure, it is mainly used for academics. Dithering and error diffusion are two categories that have been researched more extensively as a practical approach for industrial implementation. A brief review of these three methods is as follows.
(1) Dithering
Ordered dithering can be classified into two categories. The two categories are clustered-dot and dispersed-dot ordered dithering. FIG. 1(a) shows a 4×4 clustered-dot ordered dithering pattern and FIG. 1(b) shows a 4×4 dispersed-dot ordered dithering pattern. Clustered-dot ordered dithering uses variable-size halftone dots at a fixed spacing. The addition of device pixels at a dot's outer edge increases the covered area and the size of the dot. When viewed from a distance, the larger the dot size, the greater the area covered and the darker the image area. Dispersed-dot ordered dithering is preferred when the display device is capable of displaying an isolated black or white pixel. It uses a fixed-size, smaller dot at variable spacing to achieve the same effect as clustered-dot ordered dithering. Variation in dot spacing varies the number of dots in a given area, or dot frequency. In such a technique, a denser dot distribution provides a darker image area. On some display devices, each dot comprises up to four or five device pixels. Dispersed-dot ordering provides a dot distribution based upon the shade variations in the original image. The dot distribution is optimized to be the best representation possible for the particular display device.
(2) Error Diffusion
Error diffusion is an adaptive algorithm that produces patterns with different spatial frequency content depending on the input digital image value. FIG. 2 shows a prior art block diagram 200 depicting a basic error diffusion technique. This technique is disclosed in more detail in “An Adaptive Algorithm for Spatial Greyscale,” Proceedings of the Society for Information Display, volume 17, pp. 75, 1976 by R. W. Floyd and L. Steinberg. For purpose of illustration it will be assumed that the pixels of the input digital image span the range from 0 to 255. As shown in FIG. 2, the pixels of an input digital image Pi are thresholded in a threshold block 201 to produce thresholded pixels. The threshold block 201 provides a signal having a 0 for any pixel of the input digital image below the threshold, and a 255 for any pixel of the input digital image above the threshold. A difference signal generator 202 receives the signal representing the pixel of the input digital image from the threshold block 201 and also from the output of an adder 204, which will be discussed later. The difference signal generator 202 produces a difference signal representing the error 205 introduced by the thresholding process. The difference signal is multiplied by a series of error feedback weights in an error filter 203, and is provided to the adder 204 which adds the weighted difference signal to the nearby pixels that have yet to be processed. This insures that the arithmetic mean of the pixels of the halftone digital image is preserved over a local image region.
(3) Iterative Optimization
Iterative optimization methods attempt to minimize the perceived error between the continuous-tone image and the halftoned image according to some underlying models, such as the human visual system (HVS). The error is usually calculated by a weighted least square approach. Halftone images derived by this type of techniques usually have high quality at the cost of computational complexity. The iterative optimization process is shown in FIG. 3.
As the spatial resolution of an electrophorotic display (EPD) is much lower than a printer, the ordered dithering method has the lowest computation among the three methods but yields images of poor quality. The error diffusion method and the iterative optimization method provide a more pleasing image. However, the computational resources required become a major issue when these methods are used in a hand-held electronic device. For example, the computational complexity of an error diffusion method using an 8-bit recursive computation is a large loading factor in an EPD system. Therefore, it is desirable to provide an improved system and method to reduce computational complexity and provide higher image quality.